#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@Author  :   JingV
@Version :   1.0
@Contact :   None
@License :   None
@Desc    :   None
'''


class Solution(object):
    def combine(self, n, k):
        result = []

        from collections import deque
        queue = deque([([_ for _ in range(1, n + 1)], [])])

        while queue:
            nums, group = queue.popleft()

            if len(nums) + len(group) < k:
                continue

            if len(group) == k:
                if group not in result:
                    result.append(group)
                continue

            queue.append((nums[1:], group + [nums[0]]))
            queue.append((nums[1:], group))

        return result


def main():
    solution = Solution()
    tests = [(4, 2)]
    for n, k in tests:
        print(solution.combine(n, k))


if __name__ == "__main__":
    main()
